package 回溯.剑指;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 剑指II没有重复元素集合的全排列083.java
 * @createTime 2022年11月08日 19:54:00
 */
public class 剑指II没有重复元素集合的全排列083 {
	public static void main(String[] args) {
	}
	List<List<Integer>> result = new ArrayList<>();

	public List<List<Integer>> permute(int[] nums) {
		backTrace(nums,  new boolean[nums.length]);
		return result;
	}

	LinkedList<Integer> list = new LinkedList<>();

	public void backTrace(int[] nums, boolean[] used) {
		//结束条件
		if (nums.length == list.size()) {
			result.add(new ArrayList<>(list));
			return;
		}
		for (int i = 0; i < nums.length; i++) {
			if (used[i]) {
				continue;
			}
			used[i] = true;
			list.add(nums[i]);
			backTrace(nums, used);
			used[i] = false;
			list.removeLast();
		}
	}
}
